/**
 * 最长重复子数组 --连续子序列
 * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 **公共的**、长度最长的子数组的长度 
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3, 2, 1] 。
 */

/**
 * 【连续】找i与i-1的关系
 * dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的子数组的最长公共子数组长度
 * dp[i][j] = dp[i-1][j-1]+1;
 * 需要 res记录出现的最大值，因为是要求连续，所以最后一个元素不一定就是最大的
 */
var findLength = function(nums1, nums2) {
  const [m,n] = [nums1.length, nums2.length];
  const dp = Array(m+1).fill().map(()=> Array(n+1).fill(0));
  let res = 0;
  for(let i=1;i<=m;i++) { //!!一定要取到m,才能保证nums1[i-1]取到最后一个元素
    for(let j=1;j<=n;j++) {
      if(nums1[i-1] == nums2[j-1]) {
        dp[i][j] = dp[i-1][j-1]+1;
      }
      res = Math.max(res, dp[i][j]);
    }
  }
  return res;
};
const nums1 = [1,2,3,2,1];
const nums2 = [3,2,1,4,7];
console.log('最长重复子数组', findLength(nums1, nums2)); //3

/**
 * 优化成一维数组
 * 压缩： dp[j]都是由dp[j - 1]推出
 * 跟背包一样，要从后向前遍历，这样避免重复覆盖
 */
/**
 * 在处理 nums2[j-1] 之前，dp[j] 可能已经被更新为以 nums2[j] 结尾的子数组的最长公共子数组长度。
 * 如果不将 dp[j] 重置为 0，那么这个值就会被错误地累加到下一轮迭代中，导致最终的结果不正确
 * 
 */
var findLength0 = function(nums1, nums2) {
  const [m,n] = [nums1.length, nums2.length];
  const dp = Array(n+1).fill(0);
  let res = 0;
  for(let i=1;i<=m; i++) {
    for(let j=n; j>0; j--) {
      if(nums1[i-1] == nums2[j-1]) {
        dp[j] = dp[j-1]+1
      } else {
        dp[j] = 0;//不相等重置0
      }
      res = Math.max(res, dp[j]) 
    }
  }
  return res;
}
console.log('最长重复子数组', findLength0(nums1, nums2)); //3
